package through;

/**
 * @author zhangjiayuan@qipeipu.com
 * @date 2019/1/6 13:44
 * @since 1.0.0
 */
public class Kmp {
    public int[] kmp(String ps){
        char[] psChar = ps.toCharArray();
        int[] next = new int[psChar.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while(j< psChar.length){
            if(k == -1|| psChar[j] == psChar[k]){
                j++;
                k++;
                next[j] = k;
            }else{
                k = next[k];
            }
        }
        return next;
    }
    public static void main(String[] args) {
        String ps = "abababca";
        int[] results = version1.Kmp.getNext(ps);
        for (int result : results) {
            System.out.print(result+" ");
        }
    }
}
